{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Design an Expression Tree With Evaluate Function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #design #math #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #设计 #数学 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: buildTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #设计带解析函数的表达式树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个算术表达式的后缀表示法的标记（token）&nbsp;<code>postfix</code>&nbsp;，构造并返回该表达式对应的二叉表达式树。</p>\n",
    "\n",
    "<p><b>后缀</b>表示法是一种将操作数写在运算符之前的表示法。例如，表达式&nbsp;<code>4*(5-(2+7))</code>&nbsp;的后缀表示法表示为数组&nbsp;<code>postfix = [\"4\",\"5\",\"7\",\"2\",\"+\",\"-\",\"*\"]</code>&nbsp;。</p>\n",
    "\n",
    "<p>抽象类&nbsp;<code>Node</code>&nbsp;需要用于实现二叉表达式树。我们将通过&nbsp;<code>evaluate</code>&nbsp;函数来测试返回的树是否能够解析树中的值。你不可以移除 <code>Node</code> 类，但你可以按需修改此类，也可以定义其他类来实现它。</p>\n",
    "\n",
    "<p><a href=\"https://en.wikipedia.org/wiki/Binary_expression_tree\"><strong>二叉表达式树</strong></a>是一种表达算术表达式的二叉树。二叉表达式树中的每一个节点都有零个或两个子节点。&nbsp;叶节点（有 0 个子节点的节点）表示操作数，非叶节点（有 2 个子节点的节点）表示运算符：&nbsp;<code>'+'</code>&nbsp;（加）、&nbsp;<code>'-'</code> （减）、&nbsp;<code>'*'</code> （乘）和&nbsp;<code>'/'</code> （除）。</p>\n",
    "\n",
    "<p>我们保证任何子树对应值的绝对值不超过&nbsp;<code>10<sup>9</sup></code>&nbsp;，且所有操作都是有效的（即没有除以零的操作）</p>\n",
    "\n",
    "<p><b>进阶：</b>&nbsp;你可以将表达式树设计得更模块化吗？例如，你的设计能够不修改现有的&nbsp;<code>evaluate</code>&nbsp;的实现就能支持更多的操作符吗？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/15/untitled-diagram.png\" style=\"width: 242px; height: 241px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b> s = [\"3\",\"4\",\"+\",\"2\",\"*\",\"7\",\"/\"]\n",
    "<b>输出：</b> 2\n",
    "<b>解释：</b> 此表达式可解析为上述二叉树，其对应表达式为 (<code>(3+4)*2)/7) = 14/7 = 2.</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/15/untitled-diagram2.png\" style=\"width: 222px; height: 232px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = [\"4\",\"5\",\"7\",\"2\",\"+\",\"-\",\"*\"]\n",
    "<strong>输出:</strong> -16\n",
    "<strong>解释:</strong> 此表达式可解析为上述二叉树，其对应表达式为 4*(5-<code>(2+7)) = 4*(-4) = -16.</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt; 100</code></li>\n",
    "\t<li><code>s.length</code>&nbsp;是奇数。</li>\n",
    "\t<li><code>s</code>&nbsp;包含数字和字符&nbsp;<code>'+'</code>&nbsp;、&nbsp;<code>'-'</code>&nbsp;、&nbsp;<code>'*'</code>&nbsp;以及&nbsp;<code>'/'</code>&nbsp;。</li>\n",
    "\t<li>如果&nbsp;<code>s[i]</code>&nbsp;是数，则对应的整数不超过&nbsp;<code>10<sup>5</sup></code>&nbsp;。</li>\n",
    "\t<li><code>s</code>&nbsp;保证是一个有效的表达式。</li>\n",
    "\t<li>结果值和所有过程值的绝对值均不超过&nbsp;<code>10<sup>9</sup></code>&nbsp;。</li>\n",
    "\t<li>保证表达式不包含除以零的操作。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [design-an-expression-tree-with-evaluate-function](https://leetcode.cn/problems/design-an-expression-tree-with-evaluate-function/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [design-an-expression-tree-with-evaluate-function](https://leetcode.cn/problems/design-an-expression-tree-with-evaluate-function/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"3\",\"4\",\"+\",\"2\",\"*\",\"7\",\"/\"]', '[\"4\",\"5\",\"2\",\"7\",\"+\",\"-\",\"*\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        isroot=set()\n",
    "        tree_dic=collections.defaultdict(list)\n",
    "        for p, ch, l in descriptions:\n",
    "            tree_dic[p].append([ch, l])\n",
    "            if ch not in isroot:\n",
    "                isroot.add(ch)\n",
    "            \n",
    "        for k in tree_dic.keys():\n",
    "            if k not in isroot:\n",
    "                root_val=k\n",
    "                break\n",
    "        \n",
    "        def buildTree(root_val:int):\n",
    "            root=TreeNode(root_val)\n",
    "            for v in tree_dic[root_val]:\n",
    "                if v[1]==1:\n",
    "                    root.left=buildTree(v[0])\n",
    "                else:\n",
    "                    root.right=buildTree(v[0])\n",
    "            return root\n",
    "        \n",
    "        return buildTree(root_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import abc \n",
    "from abc import ABC, abstractmethod \n",
    "\"\"\"\n",
    "This is the interface for the expression tree Node.\n",
    "You should not remove it, and you can define some classes to implement it.\n",
    "\"\"\"\n",
    "\n",
    "class Node(ABC):\n",
    "    @abstractmethod\n",
    "    # define your fields here\n",
    "    def evaluate(self) -> int:\n",
    "        pass\n",
    "\n",
    "\n",
    "class TreeNode(Node):\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "    def evaluate(self) -> int:\n",
    "        if self.val is None:\n",
    "            return 0\n",
    "        left, right = 0, 0\n",
    "        if self.val in '+-*/':\n",
    "            if self.left:\n",
    "                left = int(self.left.evaluate())\n",
    "            if self.right:\n",
    "                right = int(self.right.evaluate())\n",
    "            if self.val == '+':\n",
    "                return left + right\n",
    "            if self.val == '-':\n",
    "                return left - right\n",
    "            if self.val == '*':\n",
    "                return left * right\n",
    "            if self.val == '/':\n",
    "                return left // right\n",
    "        else:\n",
    "            return self.val\n",
    "\n",
    "\"\"\"    \n",
    "This is the TreeBuilder class.\n",
    "You can treat it as the driver code that takes the postinfix input\n",
    "and returns the expression tree represnting it as a Node.\n",
    "\"\"\"\n",
    "class TreeBuilder(object):\n",
    "    \n",
    "\n",
    "    def buildTree(self, postfix: List[str]) -> 'Node':\n",
    "        if not postfix:\n",
    "            return None\n",
    "        stack = []\n",
    "        for n in postfix:\n",
    "            node = TreeNode(n)\n",
    "            if n in '+-/*':\n",
    "                node.right = stack.pop()\n",
    "                node.left = stack.pop() \n",
    "            stack.append(node)\n",
    "        return stack[-1]\n",
    "\n",
    "        \n",
    "\t\t\n",
    "\"\"\"\n",
    "Your TreeBuilder object will be instantiated and called as such:\n",
    "obj = TreeBuilder();\n",
    "expTree = obj.buildTree(postfix);\n",
    "ans = expTree.evaluate();\n",
    "\"\"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import abc \n",
    "from abc import ABC, abstractmethod \n",
    "\"\"\"\n",
    "This is the interface for the expression tree Node.\n",
    "You should not remove it, and you can define some classes to implement it.\n",
    "\"\"\"\n",
    "\n",
    "class Node():\n",
    "    @abstractmethod\n",
    "    # define your fields here\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "    def evaluate(self) -> int:\n",
    "        if self.val.isdigit():\n",
    "            return int(self.val)\n",
    "        if self.val == '+':\n",
    "            return self.left.evaluate() + self.right.evaluate()\n",
    "        if self.val == '-':\n",
    "            return self.left.evaluate() - self.right.evaluate()\n",
    "        if self.val == '*':\n",
    "            return self.left.evaluate() * self.right.evaluate()\n",
    "        if self.val == '/':\n",
    "            return self.left.evaluate() // self.right.evaluate()\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"    \n",
    "This is the TreeBuilder class.\n",
    "You can treat it as the driver code that takes the postinfix input\n",
    "and returns the expression tree represnting it as a Node.\n",
    "\"\"\"\n",
    "\n",
    "class TreeBuilder(object):\n",
    "    def buildTree(self, postfix: List[str]) -> 'Node':\n",
    "        if not postfix: return None\n",
    "        node = Node(postfix.pop())\n",
    "        if node.val.isdigit():\n",
    "            return node\n",
    "        node.right = self.buildTree(postfix)\n",
    "        node.left = self.buildTree(postfix)\n",
    "        return node\n",
    "\t\t\n",
    "\"\"\"\n",
    "Your TreeBuilder object will be instantiated and called as such:\n",
    "obj = TreeBuilder();\n",
    "expTree = obj.buildTree(postfix);\n",
    "ans = expTree.evaluate();\n",
    "\"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import abc \n",
    "from abc import ABC, abstractmethod \n",
    "\"\"\"\n",
    "This is the interface for the expression tree Node.\n",
    "You should not remove it, and you can define some classes to implement it.\n",
    "\"\"\"\n",
    "\n",
    "class Node(ABC):\n",
    "    func = {'+': add, '-': sub, '*': mul, '/': floordiv}\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "    def evaluate(self) -> int:\n",
    "        if self.val in self.func:\n",
    "            return self.func[self.val](self.left.evaluate(), self.right.evaluate())\n",
    "        return self.val\n",
    "\n",
    "\"\"\"    \n",
    "This is the TreeBuilder class.\n",
    "You can treat it as the driver code that takes the postinfix input\n",
    "and returns the expression tree represnting it as a Node.\n",
    "\"\"\"\n",
    "\n",
    "class TreeBuilder(object):\n",
    "    def buildTree(self, postfix: List[str]) -> 'Node':\n",
    "        stack = []\n",
    "        for x in postfix:\n",
    "            if x in '+-*/':\n",
    "                r = stack.pop()\n",
    "                l = stack.pop()\n",
    "                stack.append(Node(x, l, r))\n",
    "            else:\n",
    "                stack.append(Node(int(x)))\n",
    "        return stack[0]\n",
    "\t\t\n",
    "\"\"\"\n",
    "Your TreeBuilder object will be instantiated and called as such:\n",
    "obj = TreeBuilder();\n",
    "expTree = obj.buildTree(postfix);\n",
    "ans = expTree.evaluate();\n",
    "\"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node():\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "    def evaluate(self) -> int:\n",
    "        if self.val.isdigit():\n",
    "            return int(self.val)\n",
    "        if self.val == '+':\n",
    "            return self.left.evaluate() + self.right.evaluate()\n",
    "        if self.val == '-':\n",
    "            return self.left.evaluate() - self.right.evaluate()\n",
    "        if self.val == '*':\n",
    "            return self.left.evaluate() * self.right.evaluate()\n",
    "        if self.val == '/':\n",
    "            return self.left.evaluate() // self.right.evaluate()\n",
    "\n",
    "class TreeBuilder(object):\n",
    "    def buildTree(self, postfix: List[str]) -> 'Node':\n",
    "        if not postfix: return None\n",
    "        node = Node(postfix.pop())\n",
    "        if node.val.isdigit():\n",
    "            return node\n",
    "        node.right = self.buildTree(postfix)\n",
    "        node.left = self.buildTree(postfix)\n",
    "        return node\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import abc\n",
    "from abc import ABC, abstractmethod\n",
    "\n",
    "\"\"\"\n",
    "This is the interface for the expression tree Node.\n",
    "You should not remove it, and you can define some classes to implement it.\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Node(ABC):\n",
    "    @abstractmethod\n",
    "    # define your fields here\n",
    "    def evaluate(self) -> int:\n",
    "        pass\n",
    "\n",
    "\n",
    "\"\"\"    \n",
    "This is the TreeBuilder class.\n",
    "You can treat it as the driver code that takes the postinfix input\n",
    "and returns the expression tree represnting it as a Node.\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class TreeBuilder(object):\n",
    "    def buildTree(self, postfix: List[str]) -> 'Node':\n",
    "        from dataclasses import dataclass\n",
    "\n",
    "        @dataclass\n",
    "        class NumericNode(Node):\n",
    "            val: int\n",
    "\n",
    "            def evaluate(self) -> int:\n",
    "                return self.val\n",
    "\n",
    "        @dataclass\n",
    "        class OperatorNode(Node):\n",
    "            val: Callable[[int, int], int]\n",
    "            right: Node\n",
    "            left: Node\n",
    "\n",
    "            def evaluate(self) -> int:\n",
    "                return self.val(self.left.evaluate(), self.right.evaluate())\n",
    "\n",
    "        operator_dict = {'+': add, '-': sub, '*': mul, '/': floordiv}\n",
    "        stack = deque()\n",
    "        for i in postfix:\n",
    "            if i in operator_dict:\n",
    "                stack.append(OperatorNode(operator_dict[i], stack.pop(), stack.pop()))\n",
    "            else:\n",
    "                stack.append(NumericNode(int(i)))\n",
    "        return stack[0]\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "Your TreeBuilder object will be instantiated and called as such:\n",
    "obj = TreeBuilder();\n",
    "expTree = obj.buildTree(postfix);\n",
    "ans = expTree.evaluate();\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import abc \n",
    "from abc import ABC, abstractmethod \n",
    "\"\"\"\n",
    "This is the interface for the expression tree Node.\n",
    "You should not remove it, and you can define some classes to implement it.\n",
    "\"\"\"\n",
    "\n",
    "class Node():\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "    # define your fields here\n",
    "    def evaluate(self) -> int:\n",
    "        if self.val.isdigit():\n",
    "            return int(self.val)\n",
    "        if self.val == '+':\n",
    "            return self.left.evaluate() + self.right.evaluate()\n",
    "        if self.val == '-':\n",
    "            return self.left.evaluate() - self.right.evaluate()\n",
    "        if self.val == '*':\n",
    "            return self.left.evaluate() * self.right.evaluate()\n",
    "        if self.val == '/':\n",
    "            return self.left.evaluate() // self.right.evaluate()\n",
    "\n",
    "\n",
    "\"\"\"    \n",
    "This is the TreeBuilder class.\n",
    "You can treat it as the driver code that takes the postinfix input\n",
    "and returns the expression tree represnting it as a Node.\n",
    "\"\"\"\n",
    "\n",
    "class TreeBuilder(object):\n",
    "    def buildTree(self, postfix: List[str]) -> 'Node':\n",
    "        if not postfix: return None\n",
    "        node = Node(postfix.pop())\n",
    "        if node.val.isdigit():\n",
    "            return node\n",
    "        node.right = self.buildTree(postfix)\n",
    "        node.left = self.buildTree(postfix)\n",
    "        return node\n",
    "        \n",
    "\t\t\n",
    "\"\"\"\n",
    "Your TreeBuilder object will be instantiated and called as such:\n",
    "obj = TreeBuilder();\n",
    "expTree = obj.buildTree(postfix);\n",
    "ans = expTree.evaluate();\n",
    "\"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import abc \n",
    "from abc import ABC, abstractmethod \n",
    "\"\"\"\n",
    "This is the interface for the expression tree Node.\n",
    "You should not remove it, and you can define some classes to implement it.\n",
    "\"\"\"\n",
    "\n",
    "class Node():\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "    # define your fields here\n",
    "    def evaluate(self) -> int:\n",
    "        if self.val.isdigit():\n",
    "            return int(self.val)\n",
    "        if self.val == '+':\n",
    "            return self.left.evaluate() + self.right.evaluate()\n",
    "        if self.val == '-':\n",
    "            return self.left.evaluate() - self.right.evaluate()\n",
    "        if self.val == '*':\n",
    "            return self.left.evaluate() * self.right.evaluate()\n",
    "        if self.val == '/':\n",
    "            return self.left.evaluate() // self.right.evaluate()\n",
    "\n",
    "\n",
    "\"\"\"    \n",
    "This is the TreeBuilder class.\n",
    "You can treat it as the driver code that takes the postinfix input\n",
    "and returns the expression tree represnting it as a Node.\n",
    "\"\"\"\n",
    "\n",
    "class TreeBuilder(object):\n",
    "    def buildTree(self, postfix: List[str]) -> 'Node':\n",
    "        if not postfix: return None\n",
    "        node = Node(postfix.pop())\n",
    "        if node.val.isdigit():\n",
    "            return node\n",
    "        node.right = self.buildTree(postfix)\n",
    "        node.left = self.buildTree(postfix)\n",
    "        return node\n",
    "        \n",
    "\t\t\n",
    "\"\"\"\n",
    "Your TreeBuilder object will be instantiated and called as such:\n",
    "obj = TreeBuilder();\n",
    "expTree = obj.buildTree(postfix);\n",
    "ans = expTree.evaluate();\n",
    "\"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import abc \n",
    "from abc import ABC, abstractmethod \n",
    "\"\"\"\n",
    "This is the interface for the expression tree Node.\n",
    "You should not remove it, and you can define some classes to implement it.\n",
    "\"\"\"\n",
    "\n",
    "class Node():\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "    \n",
    "    def evaluate(self) -> int:\n",
    "        if self.val.isdigit():\n",
    "            return int(self.val)\n",
    "        if self.val == '+':\n",
    "            return self.left.evaluate() + self.right.evaluate()\n",
    "        if self.val == '-':\n",
    "            return self.left.evaluate() - self.right.evaluate()\n",
    "        if self.val == '*':\n",
    "            return self.left.evaluate() * self.right.evaluate()\n",
    "        if self.val == '/':\n",
    "            return self.left.evaluate() // self.right.evaluate()\n",
    "\n",
    "\"\"\"    \n",
    "This is the TreeBuilder class.\n",
    "You can treat it as the driver code that takes the postinfix input\n",
    "and returns the expression tree represnting it as a Node.\n",
    "\"\"\"\n",
    "\n",
    "class TreeBuilder(object):\n",
    "    def buildTree(self, postfix: List[str]) -> 'Node':\n",
    "        if not postfix: return None\n",
    "        node = Node(postfix.pop())\n",
    "        if node.val.isdigit():\n",
    "            return node\n",
    "        node.right = self.buildTree(postfix)\n",
    "        node.left = self.buildTree(postfix)\n",
    "        return node\n",
    "\t\t\n",
    "\"\"\"\n",
    "Your TreeBuilder object will be instantiated and called as such:\n",
    "obj = TreeBuilder();\n",
    "expTree = obj.buildTree(postfix);\n",
    "ans = expTree.evaluate();\n",
    "\"\"\""
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
